package ljl.alg.jianzhioffer.round2;

/**
 * 剑指 offer 上这道题考点是大数打印，但是这道题简化的不成样子了
 *
 * ok 这是近期来我碰到的第一个不会的题，neng 它！
 * 虽然之前做过两遍了，还是不会做
 *
 * 感觉这道题会花我 2 小时！
 */
public class _17_print_1_to_max_n {
    
    /*
    * 路飞的解法，我蒙了
    * 我在第一层他在第三层，可能
    * */
    char[] num;
    int start;
    int[] res;
    int count;
    int n;
    int nine;
    public int[] printNumbers2(int n) {
        this.n = n;
        num = new char[n];
        start = n - 1;
        res = new int[(int) (Math.pow(10, n)) - 1];
        dfs(0);
        return res;
    }
    void dfs(int cur) {
        if (n == cur) {
            // 不可写成 new String(num, start, n) 第三个参数是 count，不是 end...
            String s = new String(num).substring(start);
            // 这句不可或缺
            if ("0".equals(s)) return;
            res[count++] = Integer.parseInt(s);
            if (n - nine == start) start--;
            return;
        }
        for (char i = '0'; i <= '9'; i++) {
            if (i == '9') nine++;
            num[cur] = i;
            dfs(cur + 1);
        }
        nine--;
    }
    
    /*
    * 这个解法很好，技巧性比较强！
    * 更慢了！比路飞的还慢两毫秒，那确实慢！
    * */
    int[] nums;
    int index;
    StringBuilder c = new StringBuilder();
    public int[] printNumbers(int n) {
        nums = new int[(int) Math.pow(10, n) - 1];
        for (int i = 1; i <= n; i++) {
            back(0, i);
        }
        return nums;
    }
    void back(int x, int len) {
        if (len == x) {
            nums[index++] = Integer.parseInt(c.toString());
            return;
        }
        int start = x == 0 ? 1 : 0;
        for (int i = start; i <= 9; i++) {
            c.append(i);
            back(x + 1, len);
            c.deleteCharAt(c.length() - 1);
        }
    }
}
